package com.tgy.leetcode;

import java.util.Arrays;

class NumMatrix {

    private int[][] sums;

    public NumMatrix(int[][] matrix) {

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }

        int row = matrix.length;
        int col = matrix[0].length;

        sums = new int[row + 1][col + 1];

        for (int i = 1; i <= row; i++) {

            for (int j = 1; j <= col; j++) {

                sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i - 1][j-1] + matrix[i-1][j-1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {

        if (sums == null) {

            return 0;
        }

        return sums[row2 + 1][col2 + 1] - sums[row2+1][col1] - sums[row1][col2 + 1] + sums[row1][col1];
    }
}


public class _304_二维区域和检索_矩阵不可变 {

    public static void main(String[] args) {

        int[][] matrix = {
                {3, 0, 1, 4, 2},
                {5, 6, 3, 2, 1},
                {1, 2, 0, 1, 5},
                {4, 1, 0, 1, 7},
                {1, 0, 3, 0, 5}
        };

        NumMatrix numMatrix = new NumMatrix(matrix);

        System.out.println(numMatrix.sumRegion(2, 1, 4, 3));
        System.out.println(numMatrix.sumRegion(1, 1, 2, 2));
        System.out.println(numMatrix.sumRegion(1, 2, 2, 4));

    }
}
